package leetcode_en

import (
	lc "go-study/src/leetcode"
	"go-study/src/utils"
)

/*
题目来源:https://blog.csdn.net/ATFWUS/article/details/106193067
*/

/**
 * @Description: 198. 打家劫舍
 * @Keyword: 动态打劫
 * @Author: kami
 * @Date: 2022/3/20 8:57
 **/
func rob(nums []int) int {
	dp := make([][]int, len(nums))
	// 0 不抢，1抢
	dp[0] = []int{0, nums[0]}
	var max = nums[0]
	for i := 1; i < len(nums); i++ {
		notRob := utils.GetMax(dp[i-1][0], dp[i-1][1])
		robVal := dp[i-1][0] + nums[i]
		dp[i] = []int{notRob, robVal}
		max = utils.GetMax(max, utils.GetMax(notRob, robVal))
	}

	return max
}

/**
 * @Description: 337. 打家劫舍 III 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/11 21:51
 **/
func rob337(root *lc.TreeNode) int {
	var result = rob337Dfs(root)
	return utils.GetMax(result[0], result[1])
}

func rob337Dfs(node *lc.TreeNode) [2]int {
	if node == nil {
		return [2]int{}
	}
	var result = [2]int{}
	var left = rob337Dfs(node.Left)
	var right = rob337Dfs(node.Right)
	result[0] = utils.GetMax(left[0], left[1]) + utils.GetMax(right[0], right[1])
	result[1] = left[0] + right[0] + node.Val
	return result
}

/**
 * @Description: 322. 零钱兑换
 * @Keyword: 冬天
 * @Author: kami
 * @Date: 2022/3/20 10:43
 **/
func coinChange(coins []int, amount int) int {
	var maxA = amount + 1
	// dp[i]表示组成金额i需要的最少硬币数
	dp := make([]int, maxA)
	for i := 0; i < maxA; i++ {
		dp[i] = maxA
	}
	dp[0] = 0
	for i := 0; i < len(coins); i++ {
		for j := 0; j <= amount; j++ {
			// 所求金额大于当前硬币面额才更新
			if j >= coins[i] {
				// 所求金额需要的最小硬币数是 1.上次计算出来的数值 2.目标金额减去当前硬币面额所用的最小硬币数 + 1
				dp[j] = utils.GetMin(dp[j], dp[j-coins[i]]+1)
			}
		}
	}

	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

/**
 * @Description: 518. 零钱兑换 II
 * @Keyword:
 * @Author: kami
 * @Date: 2022/3/21 21:14
 **/
func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1
	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] += dp[i-coin]
		}
	}
	return dp[amount]
}

/**
 * @Description: 300. 最长递增子序列
 * @Keyword: 严格递增子序列,非连续的
 * @Author: kami
 * @Date: 2022/3/31 21:46
 **/
func lengthOfLIS(nums []int) int {
	dp := []int{}
	for _, num := range nums {
		if len(dp) == 0 || dp[len(dp)-1] < num {
			dp = append(dp, num)
		} else {
			l, r := 0, len(dp)-1
			pos := r
			for l <= r {
				mid := (l + r) >> 1
				if dp[mid] >= num {
					pos = mid
					r = mid - 1
				} else {
					l = mid + 1
				}
			}
			dp[pos] = num
		}
	}
	return len(dp)
}

/**
 * @Description: 983. 最低票价
 * @Keyword: 记忆化搜索
 * @Author: kami
 * @Date: 2022/4/3 9:24
 **/
func mincostTickets(days []int, costs []int) int {
	var length = len(days)
	var maxDay = days[length-1]
	var minDay = days[0]
	var dp = make([]int, maxDay+31)
	i := length - 1
	for d := maxDay; d >= minDay; d-- {
		if d == days[i] {
			dp[d] = utils.GetMin(dp[d+1]+costs[0], dp[d+7]+costs[1])
			dp[d] = utils.GetMin(dp[d], dp[d+30]+costs[2])
			i--
			continue
		}
		dp[d] = dp[d+1]
	}
	return dp[minDay]
}
